SOS2 Encoding
Type : Selection
Range : The settings listed below
Default : Automatic
This option controls the automatic reformulation of SOS2 constraints. Such constraints can be handled directly by the MIP branch-and-cut algorithm, but they are often handled more efficiently by reformulating them using binary or integer variables. There are several different ways to perform this reformulation; they differ in their size and strength. Smaller reformulations add fewer variables and constraints to the model. Stronger reformulations reduce the number of branch-and-cut nodes required to solve the resulting model.
Possible values are:
Automatic
Multiple choice model
Incremental model
Logarithmic, emphasize LP relaxation
Logarithmic, emphasize branching
Settings ‘Multiple choice model’ and ‘Incremental model’ of this option encode an SOS2 constraint using a formulation whose size is linear in the number of SOS members. Setting ‘Multiple choice model’ uses a so-called multiple choice model. It usually produces an LP relaxation that is easier to solve. Setting ‘Incremental model’ uses an incremental model. It often gives a stronger representation, reducing the amount of branching required to solve harder problems.
Settings ‘Logarithmic, emphasize LP relaxation’ and ‘Logarithmic, emphasize branching’ of this option encode the SOS2 using a formulation of logarithmic size. They both only apply when all the variables in the SOS2 are non-negative. Setting ‘Logarithmic, emphasize branching’ additionally requires that the sum of the variables in the SOS2 is equal to 1. Logarithmic formulations are often advantageous when the SOS2 constraint has a large number of members. Setting ‘Logarithmic, emphasize LP relaxation’ focuses on a formulation whose LP relaxation is easier to solve, while setting ‘Logarithmic, emphasize branching’ has better branching behaviour.
The default value chooses a reformulation for each SOS2 constraint automatically.
Note
The reformulation of SOS2 constraints is also influenced by the SOS2 Reformulation Threshold option. To shut off the reformulation entirely you should set that option to 0.
Learn more about